package basis.netease.medium;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 7-12 二叉树的中序遍历
 * 给定一个二叉树的根节点root，返回它的中序遍历结果。
 * 输入格式:
 * 给定一个二叉树的根节点root。
 * 树上的节点数满足 0 <= n <= 1000, 每个节点的值满足 -1000 <= val <= 1000
 * 输出格式:
 * 输出中序遍历后结果。
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 1,null,2,3
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 中序遍历后，结果输出为：1，3，2
 * 1,3,2
 */
public class Main_11 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] a = scanner.nextLine().split(",");
        TreeNode treeNode = buildTree(a);
        StringBuilder sb = new StringBuilder();
        inorder(treeNode, sb);
        System.out.println(sb.substring(0, sb.length() - 1));
    }

    public static void inorder(TreeNode root, StringBuilder sb) {
        if (root != null) {
            // 首先递归遍历左子树
            inorder(root.left, sb);
            // 然后访问根节点
            sb.append(root.value).append(",");
            // 最后递归遍历右子树
            inorder(root.right, sb);
        }
    }

    static class TreeNode {
        String value;
        TreeNode left;
        TreeNode right;

        TreeNode(String value) {
            this.value = value;
        }
    }

    private static TreeNode buildTree(String[] values) {
        if (values[0].equals("null")) {
            return null;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(values[0]);
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode current = queue.poll();
            if (!values[i].equals("null")) {
                current.left = new TreeNode(values[i]);
                queue.offer(current.left);
            }
            i++;
            if (i < values.length && !values[i].equals("null")) {
                current.right = new TreeNode(values[i]);
                queue.offer(current.right);
            }
            i++;
        }
        return root;
    }

}
